#include <bits/stdc++.h>
using namespace std;

class Solution {
    int HS(vector<int>& nums, int target){
        // nums.empty()
        if(nums.empty()) return 0;
        
        int left = 0; int right = nums.size() - 1;
        int mid = (left + right) >> 1;
        while(left <= right){
            mid = (left + right) >> 1;
            if(nums[mid] == target) break;
            if(nums[mid] < target) left = mid + 1;
            if(nums[mid] > target) right = mid - 1;
        }
        if(nums[mid] == target) return mid;
        else if(nums[mid] < target) return mid + 1;
        else if(nums[mid] > target) return mid; // insert to the head pos
        else return 0;
    }
public:
    int searchInsert(vector<int>& nums, int target) {
        return HS(nums, target);
    }
};

int main(){
    vector<int> nums = {1,3,5,6};
    int target = 7;
    Solution solution;
    auto ans = solution.searchInsert(nums, target);
    return 0;
}